package sort.leetcode;

/**
 * @author shkstart
 * @create 2022-11-10-22:16
 */
public class Num215 {
    public int findKthLargest(int[] nums, int k) {

//        第k大元素的索引为n-k
//        [1,2,3,4,5]第二大元素的索引为5-2=3;
         return findKthLargestInternal(nums,0,nums.length-1,nums.length-k);
    }




//    在nums[l...r]找到索引为k 的元素
    private int findKthLargestInternal(int[] nums, int l, int r, int k) {
        if (l > r) {
//            空区间
            return -1;
        }
        int p = partition(nums,l,r);
        if(p==k){
//            此时p索引对应的的元素就是我们要找的元素
            return nums[p];
        }else if(k> p){
//            我们从右半区域寻找
            return findKthLargestInternal(nums,p+1,r,k);
        }
        return findKthLargestInternal(nums,l,p-1,k);
         

    }

    private int partition(int[] nums, int l, int r) {

//        默认选择第一个元素作为分区点
        int v= nums[l];
//        i是当前正处理的元素
//        arr[l+1,,j]<v 为空
        int j = l;
//        arr[j+1,,,i]<v 为空
        for (int i = l+1; i <=r ; i++) {
            if(nums[i]<v){
                swap(nums,j+1,i);
                j++;
            }

        }
        swap(nums,l,j);



        return j;
    }

    private void swap(int[] nums, int i, int i1) {
        int temp= nums[i];
        nums[i] = nums[i1];
        nums[i1] = temp;
    }
}
